package com.datastructure.test.recall.generatebrackets;

import java.util.ArrayList;

public class GenerateBrackets {
    ArrayList<String> res = new ArrayList<>();
    int indexN;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        indexN = n;
        dfs("",0,0);
        return res;
    }

    public void dfs(String s,int cnt1,int cnt2){
        if(cnt1 == indexN && cnt2 == indexN){
            res.add(s);
            return;
        }

        if(cnt1 < indexN) {
            dfs(s+"(",cnt1+1,cnt2);
        }

        if(cnt1 > cnt2 && cnt2 < indexN) {
            dfs(s+")",cnt1,cnt2+1);
        }
    }
}
